#define _CRT_SECURE_NO_WARNINGS	


typedef int DataType;
typedef struct Stack
{
    DataType* arr;
    int top;
    int capacity;
}Stack;

void Init_Stack(Stack* st)
{
    st->arr = NULL;
    st->top = st->capacity = 0;
}

void Destory_Stack(Stack* st)
{
    if (st->arr)
        free(st->arr);
    st->arr = NULL;
    st->top = st->capacity = 0;
}

bool Empty_Stack(Stack* st)
{
    assert(st);
    return st->top != 0;
}

void Push_Stack(Stack* st, DataType x)
{
    assert(st);
    if (st->top == st->capacity)
    {
        int newcapacity = st->capacity ? 2 * st->capacity : 4;
        DataType* tmp = (DataType*)realloc(st->arr, newcapacity * sizeof(DataType));
        if (!tmp)
        {
            perror("realloc fail!");
            exit(1);
        }
        st->arr = tmp;
        st->capacity = newcapacity;
    }
    st->arr[st->top++] = x;
}

void Pop_Stack(Stack* st)
{
    assert(Empty_Stack(st));
    st->top--;
}

DataType Get_Top_Stack(Stack* st)
{
    assert(Empty_Stack(st));
    return st->arr[st->top - 1];

}

int Count_Stack(Stack* st)
{
    assert(st);
    return st->top;
}

typedef struct
{
    Stack pushst;
    Stack popst;
} MyQueue;

MyQueue* myQueueCreate()
{
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    Init_Stack(&queue->pushst);
    Init_Stack(&queue->popst);
    return queue;
}

void myQueuePush(MyQueue* obj, int x)
{
    Push_Stack(&obj->pushst, x);
}

int myQueuePop(MyQueue* obj)
{
    DataType ret;
    if (Empty_Stack(&obj->popst))
    {
        ret = Get_Top_Stack(&obj->popst);
        Pop_Stack(&obj->popst);
    }
    else
    {
        while (Empty_Stack(&obj->pushst))
        {
            Push_Stack(&obj->popst, Get_Top_Stack(&obj->pushst));
            Pop_Stack(&obj->pushst);
        }
        ret = Get_Top_Stack(&obj->popst);
        Pop_Stack(&obj->popst);
    }
    return ret;
}

int myQueuePeek(MyQueue* obj)
{
    DataType ret;
    if (Empty_Stack(&obj->popst))
    {
        ret = Get_Top_Stack(&obj->popst);
    }
    else
    {
        while (Empty_Stack(&obj->pushst))
        {
            Push_Stack(&obj->popst, Get_Top_Stack(&obj->pushst));
            Pop_Stack(&obj->pushst);
        }
        ret = Get_Top_Stack(&obj->popst);
    }
    return ret;
}

bool myQueueEmpty(MyQueue* obj)
{
    return (!Empty_Stack(&obj->pushst)) && (!Empty_Stack(&obj->popst));
}

void myQueueFree(MyQueue* obj)
{
    Destory_Stack(&obj->pushst);
    Destory_Stack(&obj->popst);
    free(obj);
    obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/
